﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

using Ingenious.Graph;

namespace Ingenious.Core
{
    /// <summary>
    /// Serializes Ingenious Triple objects to Turtle format RDF notation
    /// Useful help at http://www.w3.org/2007/02/turtle/primer/
    /// 
    /// For a full definition of the format see http://www.w3.org/TR/turtle/
    /// 
    /// Still to implement:
    /// - '#' comment tokens
    /// - Addition of language and XSD type to triple (optional fields)
    /// - Multi-line literal objects
    /// - RDF collections
    /// </summary>
    public class TurtleSerializer : IRdfSerializer
    {
        #region Supporting Classes
        private enum TurtleTokenType
        {
            BaseUri,
            Prefix,
            SimpleTriple,
            TriplePredicateListStart,
            TriplePredicateListEntry,
            TriplePredicateListEnd,
            Comment,
            Skipped,
        }

        private class TurtleTokenLineInfo
        {
            private int m_lineLength;
            private int m_separatorLength;
            private TurtleTokenType m_turtleTokenType;

            #region Object Lifetime
            public TurtleTokenLineInfo(int lineLength, int separatorLength, TurtleTokenType turtleTokenType)
            {
                m_lineLength = lineLength;
                m_separatorLength = separatorLength;
                m_turtleTokenType = turtleTokenType;
            }
            #endregion

            #region Properties
            public int LineLength
            {
                get { return m_lineLength; }
            }

            public int SeparatorLength
            {
                get { return m_separatorLength; }
            }

            public TurtleTokenType TurtleTokenType
            {
                get { return m_turtleTokenType; }
            }
            #endregion
        }
        #endregion

        #region Constants
        private const string PrefixStringFormat = @"@prefix {0}: <{1}>" + TurtleLineSectionTerminatorSeparator;
        private const string TripleStringFormat = @"{0} {1} {2}" + TurtleLineSectionTerminatorSeparator;

        private const string TrueBooleanValue = "true";
        private const string FalseBooleanValue = "false";               

        private const string TurtleLineSectionTerminatorSeparator = " .";
        private const string TurtleLineTripleSubjectGroupSeparator = " ;";

        private const string PrefixLineStart = "@prefix ";

        private const string TurtleAbsoluteUriFormat = "<{0}>";
        private const string TurtleRDFTypeURIShorthand = "a";

        private const string TurtleLanguageTagDoubleQuotesPrefix = "\"@";
        private const string TurtleLanguageTagSingleQuotesPrefix = "'@";

        private const string TurtleXsdTypeDoubleQuotesPrefix = "\"^^";
        private const string TurtleXsdTypeSingleQuotesPrefix = "'^^";

        private const string TurtleMultiLineDoubleQuotes = "\"\"\"";
        private const string TurtleMultiLineSingleQuotes = "'''";

        private static readonly Regex m_namespacePrefixRegex = new Regex("[a-zA-Z0-9]+:", RegexOptions.Compiled);
        private static readonly Regex m_namespacePrefixUriRegex = new Regex("[a-zA-Z0-9]+:[a-zA-Z0-9]+", RegexOptions.Compiled);
       
        private const int ExpectedPrefixTokens = 3;
        private const int ExpectedTripleTokens = 3;
        private const int ExpectedGroupTripleTokens = 2;

        #region Error Constants
        private const string UnexpectedPrefixLineError = "Unexpected prefix defined ('{0}') after triples being defined. Prefixes must be defined first in a Turtle document";
        private const string UnrecognisedSyntaxLineError = "Unrecognised line syntax ('{0}')";
        private const string UnrecognisedPrefixLineSyntaxError = "Unrecognised prefix line syntax ('{0}')";
        private const string UnrecognisedTripleLineSyntaxError = "Unrecognised triple line syntax ('{0}')";
        private const string UnexpectedPrefixTokensError = "Unexpected number of prefix tokens ('{0}')";
        private const string UnexpectedTripleTokensError = "Unexpected number of triple tokens ('{0}')";
        private const string UnrecognisedPrefixSpecifierError = "Unrecognised prefix specifier ('{0}')";
        private const string UnexpectedUriStringError = "Expected URI string '{0}' to begin and end with angle brackets";
        private const string UnrecognisedUriFormatError = "Unrecognised URI format '{0}'";
        private const string UnrecognisedPrefixedUriError = "Unrecognised prefixed URI format '{0}'";
        private const string UnrecognisedLiteralValueError = "Unrecognised literal value specifier '{0}'";
        private const string UnmatchedPrefixError = "Unrecognised prefix in relative URI '{0}'";
        private const string InvalidLineTerminatorForPredixDefinitionError = "Invalid line terminator for prefix definition";
        private const string InvalidXSDTypeForLiteralValue = "Invalid XSD type specified for literal value";
        private const string NoTerminatingQuoteInToken = "No terminating quote found in token '{0}'";
        private const string UnexpectedObjectList = "Did not expect object list for compoment '{0}'. Only expected for object definition.";
        #endregion

        #endregion

        #region Serialization
        private void SerializeNamespaces(NamespaceUriCollection namespaceUriCollection, StringBuilder rdfDocumentBuilder)
        {
            if (namespaceUriCollection.Any())
            {
                foreach (NamespaceUri namespaceUri in namespaceUriCollection)
                {
                    rdfDocumentBuilder.AppendLine(string.Format(PrefixStringFormat, namespaceUri.NamespacePrefix, namespaceUri.Uri.ToString()));
                }

                // Append some white space
                rdfDocumentBuilder.AppendLine(string.Empty);
            }
        }

        private string SerializeTriple(NamespaceUriCollection namespaceUriCollection, Triple triple)
        {
            string subjectString = triple.Subject.ToString();
            string predicateString = triple.Predicate.ToString();
            string objectString = triple.IsLiteral ? ("\"" + triple.Value.ToString() + "\"") : triple.Object.ToString();

            bool subjectMatch = false;
            bool predicateMatch = false;
            bool objectMatch = triple.IsLiteral;

            foreach (NamespaceUri namespaceUri in namespaceUriCollection)
            {
                if (!subjectMatch)
                {
                    if (subjectString.StartsWith(namespaceUri.Uri.ToString()))
                    {
                        subjectString = subjectString.Replace(namespaceUri.Uri.ToString(), namespaceUri.NamespacePrefix + ":");
                        subjectMatch = true;
                    }
                }

                if (!predicateMatch)
                {
                    if (predicateString.StartsWith(namespaceUri.Uri.ToString()))
                    {
                        predicateString = predicateString.Replace(namespaceUri.Uri.ToString(), namespaceUri.NamespacePrefix + ":");
                        predicateMatch = true;
                    }
                }

                if (!objectMatch)
                {
                    if (objectString.StartsWith(namespaceUri.Uri.ToString()))
                    {
                        objectString = objectString.Replace(namespaceUri.Uri.ToString(), namespaceUri.NamespacePrefix + ":");
                        objectMatch = true;
                    }
                }

                if (subjectMatch && predicateMatch && objectMatch)
                {
                    break;
                }
            }

            if (!subjectMatch)
            {
                subjectString = string.Format(TurtleAbsoluteUriFormat, subjectString);
            }

            if (!predicateMatch)
            {
                predicateString = string.Format(TurtleAbsoluteUriFormat, predicateString);
            }

            if (!objectMatch)
            {
                objectString = string.Format(TurtleAbsoluteUriFormat, objectString);
            }

            return string.Format(TripleStringFormat, subjectString, predicateString, objectString);
        }
        #endregion

        #region Deserialization

        private bool TryGetQuotedComponent(string component, string quoteCharacter, int lastNonWhiteSpaceIndex, out string quotedComponent, out int endQuotedComponentIndex, out string error)
        {
            error = null;
            quotedComponent = null;
            endQuotedComponentIndex = -1;

            int endQuoteIndex = component.IndexOf(quoteCharacter, 1);

            if (endQuoteIndex == -1)
            {
                error = string.Format(NoTerminatingQuoteInToken, component);
                return false;
            }

            // Now find the next non-whitespace character after the end quote - could be
            // e.g. a language tag or an XSD type URI after the end quote
            if (endQuoteIndex != component.Length - 1)
            {
                endQuotedComponentIndex = component.IndexOf(endQuoteIndex + 1, c => char.IsWhiteSpace(c));

                // May be that this is the last component in the turtle line
                if (endQuotedComponentIndex == -1)
                {
                    endQuotedComponentIndex = component.Length - 1;
                }
            }
            else
            {
                endQuotedComponentIndex = endQuoteIndex;
            }

            quotedComponent = component.Substring(0, endQuotedComponentIndex + 1);
            return true;
        }

        private bool TryGetObjectListComponent(string component, out string[] objectListComponents, out string error)
        {
            objectListComponents = null;
            error = null;

            bool isInQuote = false;
            bool isInMultiLineQuote = false;

            bool lastCharacterWhiteSpace = false;

            int lastTerminatorIndex = 0;
            List<string> objectListComponentList = new List<string>();

            int charIndex = 0;

            foreach (char c in component)
            {                                    
                // Detect if we are in the scope of single or multi-line quote, in which
                // case we can ignore comma separators as they are permitted
                if (c == '"')
                {
                    if (!isInQuote)
                    {
                        if (charIndex > 1)
                        {
                            if (isInMultiLineQuote)
                            {
                                if (component.IndexOf(TurtleMultiLineDoubleQuotes, charIndex - 2) == charIndex)
                                {
                                    isInQuote = false;
                                    isInMultiLineQuote = false;
                                }
                            }
                            else
                            {
                                isInQuote = true;
                            }
                        }
                    }
                    else
                    {
                        if (component.IndexOf(TurtleMultiLineDoubleQuotes, charIndex) == charIndex)
                        {
                            isInMultiLineQuote = false;
                        }

                        isInQuote = false;
                    }
                }
                else if (c == '\'')
                {
                    if (!isInQuote)
                    {
                        if (charIndex > 1)
                        {
                            if (isInMultiLineQuote)
                            {
                                if (component.IndexOf(TurtleMultiLineSingleQuotes, charIndex - 2) == charIndex)
                                {
                                    isInQuote = false;
                                    isInMultiLineQuote = false;
                                }
                            }
                            else
                            {
                                isInQuote = true;
                            }
                        }
                    }
                    else
                    {
                        isInQuote = true;

                        if (component.IndexOf(TurtleMultiLineSingleQuotes, charIndex) == charIndex)
                        {
                            isInMultiLineQuote = true;
                        }
                    }
                }

                if(!isInQuote)
                {
                    if (c == ',')
                    {
                        objectListComponentList.Add(component.Substring(lastTerminatorIndex, (charIndex - lastTerminatorIndex)));
                        lastTerminatorIndex = charIndex + 1;

                        lastCharacterWhiteSpace = false;
                    }
                    else
                    {
                        if (char.IsWhiteSpace(c))
                        {
                            lastCharacterWhiteSpace = true;
                        }
                        else if(!char.IsWhiteSpace(c))
                        {
                            if (lastCharacterWhiteSpace)
                            {
                                if (objectListComponentList.Count == 0)
                                {
                                    // Encountered the next component without a separating comma
                                    // and have not yet found any object list components - so it
                                    // is not an object list component
                                    return false;
                                }
                                else
                                {
                                    // Found the next member of the object list
                                    lastCharacterWhiteSpace = false;
                                }
                            }
                        }
                    }
                }

                ++charIndex;
            }

            if (objectListComponentList.Count > 0 &&
                charIndex - 1 != lastTerminatorIndex)
            {
                string lastComponent = component.Substring(lastTerminatorIndex, charIndex - lastTerminatorIndex);

                if (!string.IsNullOrEmpty(lastComponent))
                {
                    objectListComponentList.Add(lastComponent.Trim());
                }
            }

            if (objectListComponentList.Any())
            {
                objectListComponents = objectListComponentList.ToArray();
            }
            
            return objectListComponentList.Any();
        }

        private bool TryParseQuotedComponent(ref string component, string quoteCharacter, int lastComponentStartIndex, out int endQuotedComponentIndex, out string error)
        {
            string quotedComponent = null;

            endQuotedComponentIndex = -1;
            error = null;

            if (component.StartsWith(quoteCharacter))
            {
                if (!TryGetQuotedComponent(component, quoteCharacter, lastComponentStartIndex,
                    out quotedComponent, out endQuotedComponentIndex, out error))
                {
                    if (error != null)
                    {
                        return false;
                    }
                }
                else
                {
                    component = quotedComponent;
                }
            }

            return quotedComponent != null;
        }

        private bool TryGetComponents(string turtleRdfLine, int startComponentIndex, out List<string[]> components, out string error)
        {
            components = null;
            error = null;

            int componentIndex = startComponentIndex;
            components = new List<string[]>();

            List<string> parsedComponents = new List<string>();

            // Trim white space from beginning or end
            turtleRdfLine.Trim();

            // Get next non-whitespace character
            int lastComponentStartIndex = 0;
            string[] objectListComponents = null;

            while (lastComponentStartIndex != -1)
            {
                int startWhiteSpaceIndex = turtleRdfLine.IndexOf(lastComponentStartIndex, 
                    c => !char.IsWhiteSpace(c) && !c.Equals('\n') && !c.Equals('\r'));

                if (startWhiteSpaceIndex != -1)
                {
                    // Add any white space at the beginning of this component
                    lastComponentStartIndex += (startWhiteSpaceIndex - lastComponentStartIndex);
                }

                string component = turtleRdfLine.Substring(lastComponentStartIndex);

                // Allow white space within quotes
                if (!string.IsNullOrEmpty(component))
                {
                    string quotedComponent = null;                    
                    int endQuotedComponentIndex = -1;

                    if (!TryParseQuotedComponent(ref component, "\"", lastComponentStartIndex, out endQuotedComponentIndex, out error))
                    {
                        if (error != null)
                        {
                            return false;
                        }
                    }
                    else
                    {
                        quotedComponent = component;
                    }

                    if (!TryParseQuotedComponent(ref component, "'", lastComponentStartIndex, out endQuotedComponentIndex, out error))
                    {
                        if (error != null)
                        {
                            return false;
                        }
                    }
                    else
                    {
                        quotedComponent = component;
                    }
                    
                    if (quotedComponent == null)
                    {
                        // See if this is an object list component (comma separated)
                        if (!TryGetObjectListComponent(component, out objectListComponents, out error))
                        {
                            // Not an object list - must be a white space separated component
                            int index = component.IndexOf(c => char.IsWhiteSpace(c));

                            if (index != -1)
                            {
                                component = component.Substring(0, index);
                            }

                            if (component == TurtleRDFTypeURIShorthand)
                            {
                                component = "<" + RdfHelper.RdfTypeUri + ">";
                            }
                        }
                        else
                        {
                            // Object list - this means that each object in the list forms
                            // a triple with the same subject and predicate URIs
                            if (componentIndex != 2)
                            {
                                // Do not expect an object list to be anything but the object
                                error = string.Format(UnexpectedObjectList, SerializerHelper.FormatLineError(component));
                                return false;
                            }
                        }
                    }
                    else
                    {
                        // Just equal to the quoted component
                        component = quotedComponent;
                    }

                    lastComponentStartIndex += (component == "<" + RdfHelper.RdfTypeUri + ">") ? 1 : component.Length;
                    parsedComponents.Add(component);

                    if (lastComponentStartIndex == turtleRdfLine.Length - 1)
                    {
                        // Finished parsing the line
                        lastComponentStartIndex = -1;
                    }
                }
                else
                {
                    lastComponentStartIndex = -1;
                }

                ++componentIndex;
            }

            if (objectListComponents != null)
            {
                foreach (string objectListComponent in objectListComponents)
                {
                    // Expand the component set according to the object list
                    parsedComponents[parsedComponents.Count - 1] = objectListComponent;
                    components.Add(parsedComponents.ToArray());
                }
            }
            else
            {
                components.Add(parsedComponents.ToArray());
            }

            return true;
        }

        private int GetSeparatorLength(TurtleTokenType turtleLineType)
        {
            bool isGroupLine = turtleLineType == TurtleTokenType.TriplePredicateListStart ||
                turtleLineType == TurtleTokenType.TriplePredicateListEntry ||
                turtleLineType == TurtleTokenType.TriplePredicateListEnd;

            return isGroupLine ? TurtleLineTripleSubjectGroupSeparator.Length : TurtleLineSectionTerminatorSeparator.Length;
        }

        /// <summary>
        /// Takes into account XSD types and special cases
        /// See full definition at http://www.w3.org/TR/turtle/#literals
        /// </summary>
        private bool TryParseLiteral(string literalText, out object[] literalValues, out string languageTag, out Type literalType, out string error)
        {
            bool success = true;

            literalText = literalText.Trim();

            // Check for a quoted literal (not all literals, e.g. numbers or booleans, are enclosed in quotes)
            bool isDoubleQuotes = literalText.StartsWith("\"");
            bool isSingleQuotes = literalText.StartsWith("'");

            error = null;
            literalValues = null;

            // The language tag identifying the language of the literal text, if specified
            languageTag = null;

            // CLR equivalent of the XSD type (if specified)
            literalType = null;

            // Check if a quoted literal
            if (isDoubleQuotes ||
                isSingleQuotes)
            {
                int literalPostFixIndex = -1;
                string literalPostFix = null;

                // Check first to see if there is a post-fix indicating a language
                literalPostFixIndex = literalText.IndexOf(TurtleLanguageTagDoubleQuotesPrefix);

                if (literalPostFixIndex == -1)
                {
                    literalPostFixIndex = literalText.IndexOf(TurtleLanguageTagSingleQuotesPrefix);
                }

                if (literalPostFixIndex != -1)
                {
                    // A language tag has been specified - we have a string of a particular language
                    languageTag = literalText.Substring(literalPostFixIndex + 2, literalText.Length - (literalPostFixIndex + 2));

                    // Language has been specified, so we assume this to be text
                    literalType = typeof(string);
                }
                else
                {
                    literalPostFixIndex = literalText.IndexOf(TurtleXsdTypeDoubleQuotesPrefix);

                    if (literalPostFixIndex == -1)
                    {
                        literalPostFixIndex = literalText.IndexOf(TurtleXsdTypeSingleQuotesPrefix);
                    }

                    if (literalPostFixIndex != -1)
                    {
                        literalPostFix = literalText.Substring(literalPostFixIndex + 1, literalText.Length - (literalPostFixIndex + 1));
                        string xsdUri = literalPostFix.Substring(3, literalPostFix.Length - 4).Trim();

                        if (!xsdUri.StartsWith(XsdHelper.XsdNamespace))
                        {
                            if (!xsdUri.StartsWith(XsdHelper.XsdDefaultPrefix + ":"))
                            {
                                error = InvalidXSDTypeForLiteralValue;
                                success = false;
                            }
                            else
                            {
                                xsdUri = xsdUri.Replace(XsdHelper.XsdDefaultPrefix + ":", XsdHelper.XsdNamespace);
                            }
                        }

                        // Try and get a CLR type matching the XSD type specified
                        XsdHelper.TryGetTypeForSchemaType(xsdUri, out literalType);
                    }
                }

                // Extract the literal value, if required
                if (literalPostFixIndex != -1)
                {
                    literalText = literalText.Substring(0, literalPostFixIndex);
                }           

                bool isMultiLine = false;

                if (literalText.StartsWith(TurtleMultiLineDoubleQuotes) ||
                    literalText.StartsWith(TurtleMultiLineSingleQuotes))
                {
                    // TODO: Handle multiple lines
                    isMultiLine = true;
                }
                else
                {
                    // Trim the quotes
                    literalText = literalText.Substring(1, literalText.Length - 1);
                }

                literalValues = new object[] { literalText };
            }
            // Check for boolean value
            else if (string.Compare(literalText, TrueBooleanValue) == 0)
            {
                literalValues = new object[] { true };
            }
            else if (string.Compare(literalText, FalseBooleanValue) == 0)
            {
                literalValues = new object[] { false };
            }
            // Check for numeric value
            else
            {
                int intValue = 0;
                double doubleValue = 0.0;

                if (!int.TryParse(literalText, out intValue))
                {
                    if (double.TryParse(literalText, out doubleValue))
                    {
                        // Just validate that this was specified as double XSD type if XSD type was specified
                        if (literalType != null)
                        {
                            if (literalType != typeof(double))
                            {
                                error = InvalidXSDTypeForLiteralValue;
                                success = false;
                            }
                        }
                    }
                    else
                    {
                        // Did not qualify as any literal value under turtle
                        success = false;
                    }
                }
                else
                {
                    // Just validate that this was specified as an integer if XSD type was specified
                    if (literalType != null)
                    {
                        if (literalType != typeof(int))
                        {
                            error = InvalidXSDTypeForLiteralValue;
                            success = false;
                        }
                    }
                }
            }

            return success;
        }

        private bool TryParsePrefixLine(string turtleRdfLine, out NamespaceUri namespaceUri, out string error)
        {
            error = null;
            namespaceUri = null;
            
            string[] components = turtleRdfLine.Split();

            if (components.Count() != ExpectedPrefixTokens)
            {
                error = string.Format(UnexpectedPrefixTokensError, SerializerHelper.FormatLineError(turtleRdfLine));
                return false;
            }

            int componentIndex = 0;

            string prefix = null;
            string uriString = null;

            foreach (string component in components)
            {
                if (componentIndex == 0)
                {
                    // The prefix indicator '@prefix '
                }
                else if (componentIndex == 1)
                {
                    if (!m_namespacePrefixRegex.IsMatch(component))
                    {
                        error = string.Format(UnrecognisedPrefixSpecifierError, component);
                        return false;
                    }

                    prefix = component.Substring(0, component.Length - 1);
                }
                else if (componentIndex == 2)
                {
                    uriString = component;

                    if(!uriString.StartsWith("<") ||
                       !uriString.EndsWith(">"))
                    {
                        error = string.Format(UnexpectedUriStringError, SerializerHelper.FormatLineError(uriString));
                        return false;
                    }

                    uriString = uriString.Substring(1, uriString.Length - 2).Trim();
                }

                ++componentIndex;
            }

            Uri uri = null;
            if (!Uri.TryCreate(uriString, UriKind.Absolute, out uri))
            {
                error = string.Format(UnrecognisedUriFormatError, uriString);
                return false;
            }

            namespaceUri = new NamespaceUri(uri, prefix);

            return true;
        }

        private bool TryParseTripleLine(string turtleRdfLine, NamespaceUriCollection namespaceUriCollection, Uri subjectGroupUri, out Triple triple, out string error)
        {
            error = null;
            triple = null;

            bool isPredicateTripleListToken = subjectGroupUri != null;
            List<string[]> components = null;

            turtleRdfLine = turtleRdfLine.Trim();

            if (!TryGetComponents(turtleRdfLine, subjectGroupUri == null ? 0 : 1, out components, out error))
            {
                return false;
            }

            if (isPredicateTripleListToken)
            {
                if (components.First().Count() != ExpectedGroupTripleTokens)
                {
                    error = string.Format(UnexpectedTripleTokensError, SerializerHelper.FormatLineError(turtleRdfLine));
                    return false;
                }
            }
            else
            {
                if (components.First().Count() != ExpectedTripleTokens)
                {
                    error = string.Format(UnexpectedTripleTokensError, SerializerHelper.FormatLineError(turtleRdfLine));
                    return false;
                }
            }

            bool isLiteral = false;
            
            string subjectPrefix = null;
            string subjectUriString = null;

            if (isPredicateTripleListToken)
            {
                subjectUriString = subjectGroupUri.ToString();
            }

            string predicatePrefix = null;
            string predicateUriString = null;

            string objectPrefix = null;
            string objectUriString = null;

            string languageTag = null;
            Type literalType = null;

            foreach (string[] componentArray in components)
            {
                int componentIndex = isPredicateTripleListToken ? 1 : 0;

                foreach (string component in componentArray)
                {
                    // Check for absolute URIs
                    if (component.StartsWith("<") &&
                        component.EndsWith(">"))
                    {
                        if (componentIndex == 0)
                        {
                            subjectUriString = component.Substring(1, component.Length - 2);
                        }
                        else if (componentIndex == 1)
                        {
                            predicateUriString = component.Substring(1, component.Length - 2);
                        }
                        else if (componentIndex == 2)
                        {
                            objectUriString = component.Substring(1, component.Length - 2);
                        }
                    }
                    else
                    {
                        // Parse as relative URIs, with namespace prefix
                        if (componentIndex == 2)
                        {
                            object[] literalValues = null;
                            isLiteral = TryParseLiteral(component, out literalValues, out languageTag, out literalType, out error);

                            if (isLiteral)
                            {
                                // TODO: Handle multi-line literals here
                                objectUriString = (string)literalValues[0];
                            }
                        }

                        if (!isLiteral)
                        {
                            // Check for the prefix
                            int colonIndex = component.IndexOf(":");

                            if (colonIndex == -1)
                            {
                                error = string.Format(UnrecognisedPrefixedUriError, component);
                                return false;
                            }

                            if (!m_namespacePrefixUriRegex.IsMatch(component))
                            {
                                error = string.Format(UnrecognisedPrefixedUriError, component);
                                return false;
                            }

                            if (componentIndex == 0)
                            {
                                subjectPrefix = component.Substring(0, colonIndex);
                                subjectUriString = component.Substring(colonIndex + 1, component.Length - (colonIndex + 1));
                            }
                            else if (componentIndex == 1)
                            {
                                predicatePrefix = component.Substring(0, colonIndex);
                                predicateUriString = component.Substring(colonIndex + 1, component.Length - (colonIndex + 1));
                            }
                            else
                            {
                                objectPrefix = component.Substring(0, colonIndex);
                                objectUriString = component.Substring(colonIndex + 1, component.Length - (colonIndex + 1));
                            }
                        }
                    }

                    ++componentIndex;
                }

                bool subjectMatch = subjectPrefix == null || isPredicateTripleListToken;
                bool predicateMatch = predicatePrefix == null;
                bool objectMatch = objectPrefix == null || isLiteral;

                if (!subjectMatch ||
                    !predicateMatch ||
                    !objectMatch)
                {
                    foreach (NamespaceUri namespaceUri in namespaceUriCollection)
                    {
                        if (!subjectMatch)
                        {
                            if (string.Compare(subjectPrefix, namespaceUri.NamespacePrefix, true) == 0)
                            {
                                subjectUriString = namespaceUri.Uri + subjectUriString;
                                subjectMatch = true;
                            }
                        }

                        if (!predicateMatch)
                        {
                            if (string.Compare(predicatePrefix, namespaceUri.NamespacePrefix, true) == 0)
                            {
                                predicateUriString = namespaceUri.Uri + predicateUriString;
                                predicateMatch = true;
                            }
                        }

                        if (!objectMatch)
                        {
                            if (string.Compare(objectPrefix, namespaceUri.NamespacePrefix, true) == 0)
                            {
                                objectUriString = namespaceUri.Uri + objectUriString;
                                objectMatch = true;
                            }
                        }

                        if (subjectMatch && predicateMatch && objectMatch)
                        {
                            break;
                        }
                    }
                }

                if (!subjectMatch)
                {
                    error = string.Format(UnrecognisedPrefixedUriError, subjectPrefix);
                    return false;
                }

                if (!predicateMatch)
                {
                    error = string.Format(UnrecognisedPrefixedUriError, predicatePrefix);
                    return false;
                }

                if (!objectMatch)
                {
                    error = string.Format(UnrecognisedPrefixedUriError, objectPrefix);
                    return false;
                }

                Uri subjectUri = null;
                Uri predicateUri = null;
                Uri objectUri = null;

                if (!Uri.TryCreate(subjectUriString, UriKind.Absolute, out subjectUri))
                {
                    error = string.Format(UnrecognisedUriFormatError, subjectUriString);
                    return false;
                }

                if (!Uri.TryCreate(predicateUriString, UriKind.Absolute, out predicateUri))
                {
                    error = string.Format(UnrecognisedUriFormatError, predicateUriString);
                    return false;
                }

                if (!isLiteral)
                {
                    if (!Uri.TryCreate(objectUriString, UriKind.Absolute, out objectUri))
                    {
                        error = string.Format(UnrecognisedUriFormatError, objectUriString);
                        return false;
                    }
                }

                if (isLiteral)
                {
                    if (languageTag != null)
                    {
                        // A string literal, with a language tag specified using RFC 4646
                        triple = new Triple(subjectUri, predicateUri, objectUriString, languageTag);
                    }
                    else if (literalType != null)
                    {
                        // A literal with a specified XSD type
                        triple = new Triple(subjectUri, predicateUri, objectUriString, literalType);
                    }
                    else
                    {
                        // Simple literal triple, without language or XSD type specification
                        triple = new Triple(subjectUri, predicateUri, objectUriString);
                    }
                }
                else
                {
                    triple = new Triple(subjectUri, predicateUri, objectUri);
                }
            }

            return true;
        }

        private bool TryParseTurtleLine(ref Uri lastSubjectGroupUri, TurtleTokenType turtleLineType, string turtleRdfLine, NamespaceUriCollection namespaceUriCollection, IList<Triple> triples, out string error)
        {
            bool success = true;
            error = null;

            // Determine the line type
            if (turtleLineType == TurtleTokenType.Prefix)
            {
                NamespaceUri namespaceUri = null;

                if (!TryParsePrefixLine(turtleRdfLine, out namespaceUri, out error))
                {
                    error = string.Format(UnrecognisedPrefixLineSyntaxError, error);
                    success = false;
                }
                else
                {
                    namespaceUriCollection.Add(namespaceUri);
                }
            }
            // Start of triple subject group
            else if (turtleLineType == TurtleTokenType.TriplePredicateListStart ||
                turtleLineType == TurtleTokenType.TriplePredicateListEntry ||
                turtleLineType == TurtleTokenType.TriplePredicateListEnd )
            {
                Triple triple = null;

                if (!TryParseTripleLine(turtleRdfLine, namespaceUriCollection, lastSubjectGroupUri, out triple, out error))
                {
                    error = string.Format(UnrecognisedTripleLineSyntaxError, error);
                    success = false;
                }
                else
                {
                    if (turtleLineType == TurtleTokenType.TriplePredicateListStart)
                    {
                        lastSubjectGroupUri = triple.Subject;
                    }
                    else if (turtleLineType == TurtleTokenType.TriplePredicateListEnd)
                    {
                        lastSubjectGroupUri = null;
                    }

                    triples.Add(triple);
                }
            }
            // Full triple line (subject, predicate, object)
            else if (turtleLineType == TurtleTokenType.SimpleTriple)
            {
                Triple triple = null;

                if (!TryParseTripleLine(turtleRdfLine, namespaceUriCollection, lastSubjectGroupUri, out triple, out error))
                {
                    error = string.Format(UnrecognisedTripleLineSyntaxError, error);
                    success = false;
                }
                else
                {
                    triples.Add(triple);
                }
            }

            return success;
        }
        #endregion

        #region IRdfSerializer interface
        public string ToRdfDocument(NamespaceUriCollection namespaceUriCollection, IList<Triple> triples)
        {
            StringBuilder rdfDocumentBuilder = new StringBuilder();

            // Serialize the namespaces with corresponding namespace prefixes
            SerializeNamespaces(namespaceUriCollection, rdfDocumentBuilder);            

            foreach (Triple triple in triples)
            {
                rdfDocumentBuilder.AppendLine(SerializeTriple(namespaceUriCollection, triple));
            }

            return rdfDocumentBuilder.ToString().Trim();
        }
        
        /// <summary>
        /// Deserializes a turtle document
        /// </summary>
        public bool FromRdfDocument(string rdfDocument, out NamespaceUriCollection namespaceUriCollection, out IList<Triple> triples, out string error)
        {
            bool success = true;

            List<TurtleTokenLineInfo> turtleLineInfos = new List<TurtleTokenLineInfo>();
            StringBuilder rdfDocumentBuilder = new StringBuilder();

            namespaceUriCollection = null;
            triples = null;
            error = null;

            namespaceUriCollection = new NamespaceUriCollection();
            triples = new List<Triple>();

            // Pass 1: Determine line lengths and tokenize (conserves memory)
            int nextSeparatorIndex = 0;
            TurtleTokenType lastTurtleTokenType = TurtleTokenType.Prefix;

            while (success && nextSeparatorIndex != -1)
            {
                int separatorLength = 0;
                TurtleTokenType turtleTokenType = TurtleTokenType.Prefix;

                int groupSeparatorIndex = rdfDocument.IndexOf(TurtleLineTripleSubjectGroupSeparator, nextSeparatorIndex + 1);
                int sectionSeparatorIndex = rdfDocument.IndexOf(TurtleLineSectionTerminatorSeparator, nextSeparatorIndex + 1);

                int separatorIndex = groupSeparatorIndex > sectionSeparatorIndex ? sectionSeparatorIndex : groupSeparatorIndex;

                if (separatorIndex != -1)
                {
                    if (separatorIndex == groupSeparatorIndex)
                    {
                        separatorLength = TurtleLineTripleSubjectGroupSeparator.Length;

                        if (lastTurtleTokenType == TurtleTokenType.TriplePredicateListStart ||
                            lastTurtleTokenType == TurtleTokenType.TriplePredicateListEntry)
                        {
                            turtleTokenType = TurtleTokenType.TriplePredicateListEntry;
                        }
                        else
                        {
                            // Start of a triple subject group (predicate list)
                            turtleTokenType = TurtleTokenType.TriplePredicateListStart;
                        }
                    }
                    else
                    {
                        separatorLength = TurtleLineSectionTerminatorSeparator.Length;

                        if (lastTurtleTokenType == TurtleTokenType.TriplePredicateListStart ||
                            lastTurtleTokenType == TurtleTokenType.TriplePredicateListEntry)
                        {
                            // The end of a subject URI group
                            turtleTokenType = TurtleTokenType.TriplePredicateListEnd;
                        }
                        else
                        {
                            // Full triple line or prefix line
                            turtleTokenType = TurtleTokenType.SimpleTriple;
                        }
                    }
                }

                if (separatorIndex != -1)
                {
                    int lineLength = (nextSeparatorIndex == -1 ? separatorIndex + 1 : separatorIndex - nextSeparatorIndex);
                    string turtleLine = rdfDocument.Substring(nextSeparatorIndex, lineLength).Trim();

                    if (!string.IsNullOrEmpty(turtleLine))
                    {
                        if (turtleLine.StartsWith(PrefixLineStart, StringComparison.InvariantCultureIgnoreCase))
                        {
                            if (lastTurtleTokenType != TurtleTokenType.Prefix)
                            {
                                error = InvalidLineTerminatorForPredixDefinitionError;
                                success = false;
                            }
                            else
                            {
                                turtleTokenType = TurtleTokenType.Prefix;
                            }
                        }
                    }
                    else
                    {
                        turtleTokenType = TurtleTokenType.Skipped;
                    }

                    turtleLineInfos.Add(new TurtleTokenLineInfo(lineLength, separatorLength, turtleTokenType));
                }            

                nextSeparatorIndex = separatorIndex + separatorLength;
                lastTurtleTokenType = turtleTokenType;
            }

            Uri lastSubjectGroupUri = null;

            // Pass 2: Create triples from the parsed lines
            if (success)
            {
                int startIndex = 0;

                foreach (TurtleTokenLineInfo turtleLineInfo in turtleLineInfos)
                {
                    string turtleRdfLine = rdfDocument.Substring(startIndex, turtleLineInfo.LineLength);

                    if (!TryParseTurtleLine(ref lastSubjectGroupUri, 
                        turtleLineInfo.TurtleTokenType, turtleRdfLine.Trim(),
                        namespaceUriCollection, triples, out error))
                    {
                        success = false;
                        break;
                    }                    

                    startIndex += turtleLineInfo.LineLength + turtleLineInfo.SeparatorLength;
                }
            }

            return success;
        }
        #endregion
    }
}
